// Playing with singly-linked list

#include <cstdio>
#include <cstring>



struct Node {
  char* data;
  Node* next;
};



void 
insert_list(Node** list_address, char* x)
{
  Node *p = new Node;

  p->data = new char[strlen(x)+1];
  strcpy(p->data, x);

  p->next = *list_address;

  *list_address = p;
}




Node* 
search_list(Node* list, char* x)
{
  while (list != NULL)
    {
      if (strcmp(list->data, x) == 0)
	{
	  return list;
	}
      list = list->next;
    }

  return NULL;
}



Node* invert_list(Node* list)
{
  Node* pred = NULL;
  Node* next;
  
  while (list != NULL)
    {
      next = list->next;
      list->next = pred;
      pred = list;
      list = next;
    }

  return pred;
}



void print_list(Node* list)
{
  while (list != NULL)
    {
      puts(list->data);
      list = list->next;
    }
}

 


int main()
{
  Node* list = NULL;

  insert_list(&list, "first insertion");
  insert_list(&list, "second insertion");
  insert_list(&list, "third insertion");

  print_list(list);

  Node* p1 = search_list(list, "first insertion");

  list = invert_list(list);

  print_list(list);
};
